Conventional relational databases are typically organized according to some form of tree data structure. This allows searches for data to rapidly traverse the data structure to return and/or modify queried data. To further improve efficiency, many systems employing relational databases run queries concurrently. To prevent processes from modifying a node in the database while other processes are reading the node, and to prevent processes from reading or modifying a node while a process is modifying the node, conventional systems typically employ some form of latching. This is done to ensure that for example, a search does not go astray because a read was performed on data being modified by a concurrent process.
However, waiting for another process to finish modifying a node may delay response times of some queries. Some systems attempt to avoid taking latches by avoiding in-place modifications of data. Instead, these systems may create a modified copy of a node and then atomically swing a pointer in the parent node from the original node to the modified copy. However, this creates garbage data that needs to be collected and in some instances may be slower than modifying data in-place.